Nimで自作インタプリタ③ Evaluatorを実装した
2019/3/29
リポジトリ
evaluatorのコードとしては250行くらい。
README少し整備しないとな。
振り返り、LexerとParser
ここまで作ってきた、LexerとParserについて軽く振り返っておく。
Lexerというのは字句解析器のことで、ソースコードを読み込んで、意味のある最小単位であるTokenに分割する。
前に書いた記事からまるまるパクると、以下のようなコードを字句解析すると、
code:example
let five = 5
let ten = 10
以下のようなToken列が出力される。
code:example
[
LET,
IDENT("five"),
ASSIGN,
INT(5),
LET,
IDENT("ten"),
ASSIGN,
INT(10),
]
Parserというのは、構文解析器のことでLexerの出力したToken列を入力として、文法エラーなどをチェックしながらASTを作るもののこと。
これも前の記事がパクると、以下のようなコードから、
code:example
let hoge = 1 + 2 * 3 / 4 + 5 - 6;
以下のようなASTを作成する。
https://gyazo.com/4d5ce5d808205935b9ef6adbd3fad9d5
Evaluatorとは何か
Evaluatorは日本語では「評価器」のこと。名前の通り、評価をする。
Parserまでは、単純にToken列を見て、「文法的に正しいか」だけを見ており、なんの意味も持っていなかった。
つまり、「1 + True」という文字列は間違ってて、「1+2」という文字列は正しいことは知っているけど、この結果が「3」になるなんて知らなかった。
そこで、Evaluatorを導入することで、この文字列の集合に意味をもたせ、評価できるようにする。また、定義した関数を呼び出せるようにするのもの、これの仕事だ。変数のスコープに気をつけながら関数を扱う。
動いているところ
先日、Twitterに動いているところを投稿した。
具体的にどう実装するか
ここで実装しているevaluatorの評価戦略には、「tree-walking型インタプリタ」のものを採用している。
これはどうやら、インタプリタの原型で最も単純なものっぽい。Parserの出力したASTをそのまま辿り、数値計算や関数を実行したりする。特に最適化もしないので実行速度は遅いが、作りやすく、考えやすく、拡張性や移植性も高いもの(らしい)。
今回は採用していないが、他の評価戦略としては、Ruby v1.9以降で採用されているASTを一度バイトコード(厳密には32bitのワードコード)へ変換し、その後、just in timeで仮想マシン上で動作するものもある。
他にもそもそもASTを作らずに直接バイトコードを出力するものや、逆にASTから直接機械語に変換するものもある。
非常に興味があるので、この辺も今後調べていきたい。
具体的にコードを見てみると、だいぶ簡素にしてるが以下のような感じになっている。このeval()という関数を再帰的に呼び出すことで、評価を行う。
code:nim
proc eval*(self: PNode, env: Environment): Object =
case self.kind
of Program:
return evalProgram(self, env)
of nkExpressionStatement:
result = eval(self.Expression, env)
of 整数リテラル:
# ごにょごにょ
of 真偽値リテラル:
# ごにょごにょ
of 前置式:
# ごにょごにょ
else:
discard
eval()の関数の中身はただのcase..of文(他の言語でいうswitch文)で、parserの出力したASTノードによって条件分岐を行っている。
続き
おおまかにはインタプリタ作成自体はほぼほぼ終わった。
あとは、途中端折ったところや、実はやばめのバグが合ったりするので、そこを修正し、さらに足りない機能を拡張したりする。
例えば、型の概念を導入し、演算子に多相性を持たせたり、組み込み関数などを導入したりだ。
さいご
エラーメッセージをかわいくした
Nimには慣れてきた気もするが、まだまだNimれてないなって気もする。